class Solution
{
public:
    int minimumCost(vector<int> &start, vector<int> &target, vector<vector<int>> &specialRoads)
    {
        int roadCount = specialRoads.size();

        // 0:start, 1:target, 2i:roadStarti, 2i+1:roadEndi, 1<=i<=roadCount
        vector<unordered_map<int, int>> adjTable(2 * roadCount + 2);
        int startX = start[0];
        int startY = start[1];
        int targetX = target[0];
        int targetY = target[1];
        adjTable[0][1] = targetX + targetY - startX - startY;

        for (int i = 0; i < roadCount; ++i)
        {
            // roadi
            adjTable[2 * (i + 1)][2 * (i + 1) + 1] = specialRoads[i][4];

            // start, roadistart
            adjTable[0][2 * (i + 1)] = specialRoads[i][0] + specialRoads[i][1] - startX - startY;

            // start, roaditarget
            // adjTable[0][2 * (i + 1) + 1] = specialRoads[i][2] + specialRoads[i][3] - startX - startY;

            // roadistart, target
            // adjTable[2 * (i + 1)][1] = targetX + targetY - specialRoads[i][0] - specialRoads[i][1];

            // roaditarget, target
            adjTable[2 * (i + 1) + 1][1] = targetX + targetY - specialRoads[i][2] - specialRoads[i][3];
        }

        for (int i = 0; i < roadCount; ++i)
        {
            for (int j = i + 1; j < roadCount; ++j)
            {
                int startIX = specialRoads[i][0];
                int startIY = specialRoads[i][1];
                int targetIX = specialRoads[i][2];
                int targetIY = specialRoads[i][3];
                int startJX = specialRoads[j][0];
                int startJY = specialRoads[j][1];
                int targetJX = specialRoads[j][2];
                int targetJY = specialRoads[j][3];

                // startI startJ
                adjTable[2 * (i + 1)][2 * (j + 1)] = abs(startIX - startJX) + abs(startIY - startJY);
                adjTable[2 * (j + 1)][2 * (i + 1)] = abs(startIX - startJX) + abs(startIY - startJY);

                // targetI targetJ
                adjTable[2 * (i + 1) + 1][2 * (j + 1) + 1] = abs(targetIX - targetJX) + abs(targetIY - targetJY);
                adjTable[2 * (j + 1) + 1][2 * (i + 1) + 1] = abs(targetIX - targetJX) + abs(targetIY - targetJY);

                // startI targetJ
                adjTable[2 * (i + 1)][2 * (j + 1) + 1] = abs(startIX - targetJX) + abs(startIY - targetJY);
                adjTable[2 * (j + 1) + 1][2 * (i + 1)] = abs(startIX - targetJX) + abs(startIY - targetJY);

                // targetI startJ
                adjTable[2 * (i + 1) + 1][2 * (j + 1)] = abs(targetIX - startJX) + abs(targetIY - startJY);
                adjTable[2 * (j + 1)][2 * (i + 1) + 1] = abs(targetIX - startJX) + abs(targetIY - startJY);
            }
        }

        auto compareDist = [](pair<int, int> &p1, pair<int, int> &p2)
        {
            if (p1.second == p1.second)
            {
                return p1.first > p2.first;
            }
            return p1.second > p2.second;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(compareDist)> q(compareDist);

        q.push({0, 0});

        vector<int> minDist(2 * roadCount + 2, INT_MAX);
        while (!q.empty())
        {
            auto [position, dist] = q.top();
            q.pop();

            if (dist > minDist[position])
            {
                continue;
            }

            for (auto [nextPos, newDist] : adjTable[position])
            {
                if (minDist[nextPos] > dist + newDist)
                {
                    minDist[nextPos] = dist + newDist;
                    q.push({nextPos, dist + newDist});
                }
            }
        }
        return minDist[1];
    }
};